package _3;

public class AP_Mt {

    //编码时要:做分析，写注释，能避免bug，提高代码质量
    static public int ApMt(int[] vb, int[] ve, int[] ap) {
        if (vb==null || ve==null || ap==null)
            return -1;
        if (vb.length==0 || ve.length==0 || ap.length==0)
            return -2;

        int t, L = vb.length; // L 数组长度，活动总数
        if (L != ve.length || L != ap.length)
            return -3;

        // 安排上的最大活动数:Mst，vap排号范围：1~Mst
        // 第1个活动排号1，最后1个活动的排号Mst，取消的活动-1和0
        int[] vap = new int[L];
        int[] vbe = new int[L];  //每个活动的时长
        int[] vid = new int[L];  //活动的初始申请号(排序前) [0,L)
        for(int i=0; i<L; i++)
            vid[i] = i;

        //按ve来排序，升序排列
        for(int i=0; i<L-1; i++) {
            for(int j=0; j<L-1-i; j++) {
                if(ve[j+1]<ve[j]) {
                    t=ve[j];   ve[j]=ve[j+1];   ve[j+1]=t; //替换ve
                    t=vb[j];   vb[j]=vb[j+1];   vb[j+1]=t; //替换vb
                    t=vid[j]; vid[j]=vid[j+1]; vid[j+1]=t; //替换id
                }
            }
        }

        // 已按ve排好序。
        // 再进行活动安排ApM，达到最多活动数Mst个
        int[] vim = new int[L+1];
        // vim:安排上的活动在ve中的序号i(排序后的)
        // 其下标是m：1~Mst， vim[0]空着不用
        // vim[1]为第1个排上的活动，在ve中的序号(排序后的)

        // Mst最大时可能=L，就是申请的活动全安排了
        // 范围:1~L，int[L+1]里漏写+1 bug

        int m=0, tm=-1;
        for(int i=0; i<L; i++) {
            if( vb[i]<0  ||  840<ve[i]  ||  vb[i]>=ve[i] ) {
                vap[i] =-1; //无效活动-1，不安排
                vbe[i] = 0; //活动时长记0
                continue;
            }
            vbe[i] = ve[i]-vb[i];  //vbe每个活动的时间，后面需要
            if(m==0 || tm<vb[i]) { //b起始时间，在上一个m的结束tm后面
                vap[i]=++m;  //标安排上的序号m:1~Mst
                tm = ve[i];  //当前新安排的活动m的结束时间tm
                vim[m] = i;  //记录其在ve中的序号(ve排序后的)
            }
            else vap[i]=0;  //有冲突0，不安排
        }

        int Mst=m;
        //全部L个活动(be)，已初步安排M个活动(st)
        //s~start起始时间，t~terminate结束时间

        //下面运行算法2，ApMt
        //对第m个活动，在活动m-1和m+1中，替换出时间最长的
        //需要获取在vb ve里的序号 m-1 ~ i_   结束时间t_
        // m ~ im              m+1 ~ _i   起始时间_s
        //在[i_ +1 ,  _i)里的每个都访问
        //活动时间(be)在(t_ , _s)里的都作为候选考查
        int i_, t_,   _i, _s,   im;
        while(m>0) {
            im = vim[m]; //调整第m个活动
            if(m==1) {
                i_ = -1; //第1个活动号是0
                t_ = -1; //第1个活动起始得晚于时间-1
            } else {
                i_ = vim[m-1];//第m-1个活动，在输入里的序号i_// 当m-1=0时，vim[0]未初始化
                t_ = ve[i_];  //结束时间// 可能访问ve[-1]或ve[L]导致越界
            }

            if(m==Mst) {
                _i = L;   //ve里最后1个活动号是L-1// 可能越界（最大索引应为L-1）
                _s = 841; //最后1个活动结束得早于841
            } else {
                // bug 修复：这里需要判断 m+1 是否越界，因为 m 最大为 Mst，当 m 为 Mst 时，m+1 会越界
                _i = vim[m+1];//第m+1个活动，在输入里的序号_i
                _s = vb[_i];  //起始时间
            }

            int maxbe = vbe[im];
            int maxid = im;
            for(int i = i_+1;  i<_i;  i++) {
                if(vb[i]<=t_ || _s<=ve[i] || vap[i]<0)
                    continue;
                //i的时间be更长，替换
                if(vbe[i] > maxbe) {
                    maxid = i;
                    maxbe = vbe[i];
                } else if (vbe[i]==maxbe && vid[i]<vid[maxid]) {
                    maxid = i; //如果时间相同，替换成原申请序号小的(先申请的)
                    maxbe = vbe[i];
                }
            }
            if (maxid != im) {
                vap[im]=0;
                vap[maxid]=m;
                vim[m] = maxid;
            }
            m--;
        }

        for(int i=0; i<L; i++)
            if(vap[i]>0)
                ap[ vid[i] ]=1;
        //  vid[i] 是排序前的活动号
        return Mst;
    }



}

